package com.michael.leetcode;

import org.junit.Test;

import java.util.Arrays;

public class ModifiedList_3217 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    /**
    3217. 从链表中移除在数组中存在的节点
    给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。

    示例 1：
    输入： nums = [1,2,3], head = [1,2,3,4,5]
    输出： [4,5]
    解释：
    移除数值为 1, 2 和 3 的节点。

    示例 2：
    输入： nums = [1], head = [1,2,1,2,1,2]
    输出： [2,2,2]
    解释：
    移除数值为 1 的节点。

    示例 3：
    输入： nums = [5], head = [1,2,3,4]
    输出： [1,2,3,4]
    解释：
    链表中不存在值为 5 的节点。

    提示：
    1 <= nums.length <= 105
    1 <= nums[i] <= 105
    nums 中的所有元素都是唯一的。
    链表中的节点数在 [1, 105] 的范围内。
    1 <= Node.val <= 105
    输入保证链表中至少有一个值没有在 nums 中出现过。
     */


    // 思路 如果不是最后的节点 则
    // tmp.val = tmp.next.val;
    // tmp.next = tmp.next.next;
    public ListNode modifiedList(int[] nums, ListNode head) {
        Arrays.sort(nums);
        ListNode tmp = head;
        ListNode last = head;
        while (tmp.next != null){
            if(find(nums, tmp.val)){
                tmp.val = tmp.next.val;
                tmp.next = tmp.next.next;
            }else {
                last = tmp;
                tmp = tmp.next;
            }
        }

        if (find(nums, tmp.val)){
            last.next = null;
        }

        return head;
    }


    private boolean find(int[] nums, int c){
        int s = 0, e = nums.length-1;
        while (s <= e){
            int m = (s+e)/2;
            if (nums[m]== c){
                return true;
            }else if (nums[m] > c){
                e = m-1;
            }else {
                s = m+1;
            }
        }
        return false;
    }


    @Test
    public void test(){
        ListNode head5 = new ListNode(5);
        ListNode head4 = new ListNode(4,head5);
        ListNode head3 = new ListNode(3,head4);
        ListNode head2 = new ListNode(2, head3);
        ListNode head = new ListNode(1,head2);
        int[] nums = {1,2,3};

        modifiedList(nums, head);

    }

    @Test
    public void test1(){
        ListNode head6 = new ListNode(2);
        ListNode head5 = new ListNode(1,head6);
        ListNode head4 = new ListNode(2,head5);
        ListNode head3 = new ListNode(1,head4);
        ListNode head2 = new ListNode(2, head3);
        ListNode head = new ListNode(1,head2);
        int[] nums = {1};

        modifiedList(nums, head);

    }
}